import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-29
 * Time: 20:57
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Solution {

    /**
     方法一: 后序非递归
     中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
     后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
     因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。
     */
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode peek = stack.peek();
            cur = peek.right;
            // 右子树为空或者右子树已经被遍历过了, 才能遍历当前节点
            if (cur == null || prev == cur) {
                ans.add(peek.val);
                prev = peek;
                stack.pop();
                // 注意 遍历过的地方, cur 置为空时最终才能跳出循环终止
                cur = null;
            }
        }
        return ans;
    }


    /**
    方法二：
     morris 后序遍历
     实质是 使用 根、右、左遍历
     然后逆序结果
     注意添加结果的两个时机， 不然会重复添加根节点
     一个是确定了右子树还没有遍历时
     另一个是不存在右子树时
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode prev = cur;
            if (cur.right != null) {
                // 右子树不为空
                prev = cur.right;
                while (prev.left != null && prev.left != cur) {
                    prev = prev.left;
                }
                if (prev.left == null) {
                    // 说明右子树还没有遍历过
                    ans.add(cur.val); // 1. 这个时候添加进去
                    prev.left = cur;
                    cur = cur.right;
                } else  {
                    // 说明右子树已经被遍历过了
                    prev.left = null;
                    cur = cur.left;
                }
            } else {
                // 右子树为空, 直接遍历左子树
                ans.add(cur.val);
                cur = cur.left; // 2. 这个时候添加进去
            }
        }
        Collections.reverse(ans);
        return ans;
    }
}
